/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: user
 * Date: 2023-05-21
 * Time: 21:43
 */
public class Java0521 {

    /*
    解题思路：
    按照题目所说，进行k次旋转，每次旋转移动一个字符
    注意：k如果超过nums的长度时，对k取模
    时间复杂度: O(KN)
    思路没有问题，但是会时间复杂度会超
*/
/*
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        for(int i = 0; i < k; ++i){
            // 将数组中前n-1个元素整体往后搬移一个位置
            int last = nums[nums.length-1];
            for(int j = nums.length-1; j >= 1; --j){
                nums[j] = nums[j-1];
            }
            // 将搬移前最后一个元素放到数组0号位置
            nums[0] = last;
        }
    }
}
*/

    /*
      解题思路：使用三次逆转法，让数组旋转k次
        1. 整体逆置
        2. 逆转子数组[0, k - 1]
        3. 逆转子数组[k, size - 1]
    */
/*
    class Solution {
        void rotate(int[] nums, int left, int right){
            while(left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            rotate(nums, 0, nums.length-1);
            rotate(nums, 0, k-1);
            rotate(nums, k, nums.length-1);
        }
    }
*/

    /*
注意：C语言答案在前，Java答案在后﻿
*/

﻿///////////////////////C 答案//////////////////////////
        ﻿/*
    方法1
    解题思路：
        1. 从前往后遍历nums，找到val第一次出现的位置
        2. 将val之后的所有元素整体往前搬移，即删除该val
        3. nums中有效元素个数减少一个
    循环进行上述操作，直到nums中所有值为val的元素全部删除完
    时间复杂度:O(N^2)  空间复杂度:O(1)
*/
        #if 0
    int removeElement(int* nums, int numsSize, int val){
        //
        while(1)
        {
            // 1. 在nums中找val出现的位置
            int pos = 0;
            for(; pos < numsSize; ++pos)
            {
                if(nums[pos] == val)
                {
                    break;
                }
            }


            // 2. 检测是否找到
            if(pos == numsSize)
                break;


            // 3. 找到值为value的元素--将其删除
            for(int j = pos+1; j < numsSize; ++j)
            {
                nums[j-1] = nums[j];
            }


            numsSize--;
        }


        return numsSize;
    }
#endif



#if 0
    /*
        方法2：
        解题思路:
            1. 创建一个长度与nums相同的数组temp
            2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
            3. 将temp中所有元素拷贝回nums中
           时间复杂度: O(N)  空间复杂度: O(N)
    */
    int removeElement(int* nums, int numsSize, int val){
        // 1. 申请numSize个元素的新空间
        int* temp = (int*)malloc(sizeof(int)*numsSize);
        if(NULL == temp)
        {
            return 0;
        }


        // 2. 将nums中非value的元素搬移到temp中---尾插到temp中
        int count = 0;
        for(int i = 0; i < numsSize; ++i)
        {
            if(nums[i] != val)
            {
                temp[count] = nums[i];
                ++count;
            }
        }


        // 3. 将temp中删除val之后的所有元素拷贝到nums中
        memcpy(nums, temp, sizeof(int)*count);
        free(temp);
        return count;
    }
#endif


#if 0
    /*
        方法2优化：
        解题思路:
        因为题目说了，数组中元素个数最大为100，所以不用动态申请，至二级创建100个元素数组即可
            1. 创建一个100个元素的整形数组temp
            2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
            3. 将temp中所有元素拷贝回nums中
           时间复杂度: O(N)  空间复杂度: O(N)
    */
    int removeElement(int* nums, int numsSize, int val){
        // 1. 申请numSize个元素的新空间
        int temp[100];


        // 2. 将nums中非value的元素搬移到temp中---尾插到temp中
        int count = 0;
        for(int i = 0; i < numsSize; ++i)
        {
            if(nums[i] != val)
            {
                temp[count] = nums[i];
                ++count;
            }
        }


        // 3. 将temp中删除val之后的所有元素拷贝到nums中
        memcpy(nums, temp, sizeof(int)*count);
        return count;
    }
#endif


#if 1
    /*
        解题思路:
            1. 设置一个变量count，用来记录nums中值等于val的元素的个数
            2. 遍历nums数组，对于每个元素进行如下操作：
                a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
                b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
                    因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
                    因此次数需要将nums[i]往前搬移
            3. 返回删除之后新数组中有效元素个数

        时间复杂度：O(N)   空间复杂度：O(1)
     */
    int removeElement(int* nums, int numsSize, int val){
        int count = 0;
        for(int i = 0; i < numsSize; ++i)
        {
            if(nums[i] == val)
            {
                count++;
            }
            else
            {
                nums[i-count] = nums[i];
            }
        }


        return numsSize - count;
    }
#endif


﻿///////////////Java 答案////////////////////////////
    class Solution {
        /*
          解题思路：
             1. 从前往后遍历nums，找到val第一次出现的位置
             2. 将val之后的所有元素整体往前搬移，即删除该val
             3. nums中有效元素个数减少一个
          循环进行上述操作，直到nums中所有值为val的元素全部删除完
          时间复杂度:O(N^2)  空间复杂度:O(1)
         */
        public int removeElement1(int[] nums, int val) {
            int size = nums.length;
            int i = 0;
            while(true){
                // 1. 在nums中找val的位置
                for(i = 0; i < size; ++i){
                    if(nums[i] == val){
                         break;
                    }
                }
                if(i == size){
                    // nums中没有发现值为val的元素，直接跳出while
                    break;
                }
                // 2. 将i位置之后所有元素整体往前搬移一个位置
                for(int pos = i+1; pos < size; ++pos){
                    nums[pos-1] = nums[pos];
                }
                // 注意：一趟之后size一定要减去1，因为删除了一个val
                size--;
            }
            return size;
        }


        /*
            解题思路:
              1. 创建一个长度与nums相同的数组ret
              2. 遍历nums，将nums中所有与val不同的元素搬移到ret中
              3. 将ret中所有元素拷贝回nums中


            时间复杂度: O(N)  空间复杂度: O(N)
        */
        public int removeElement2(int[] nums, int val) {
            int[] ret = new int[nums.length];
            int size = 0;
            for(int i = 0; i < nums.length; ++i){
                if(nums[i] != val){
                    ret[size++] = nums[i];
                }
            }
            System.arraycopy(ret, 0, nums, 0, size);
            return size;
        }

        /*
           解题思路:
             1. 设置一个变量count，用来记录nums中值等于val的元素的个数
             2. 遍历nums数组，对于每个元素进行如下操作：
                  a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
                  b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
                     因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
                     因此次数需要将nums[i]往前搬移
             3. 返回删除之后新数组中有效元素个数

           时间复杂度：O(N)   空间复杂度：O(1)
        */
        public int removeElement(int[] nums, int val) {
            int count = 0;
            for(int i = 0; i < nums.length; ++i){
                if(nums[i] == val){
                    count++;
                }else{
                    nums[i - count] = nums[i];
                }
            }

            return nums.length - count;
        }
    }

    public static void main(String[] args) {

    }


}
